/***尚硅谷Java数据结构与java算法                 ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***哈希表           P89                       ***/
/***C++ 实现版本    written by Daniel           ***/

//还需要在哈希表中添加删除元素功能

#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;

//雇员的构造
class Emp
{
public:
	//删除默认构造和拷贝构造
	Emp() = delete;
	Emp(Emp &) = delete;
	//列表初始化
	Emp(int id, string name) : id(id), name(name) {}
	//类内的元素
	int id;
	string name;
	Emp *next;
};
//雇员的链表
class EmpLinkedList
{
public:
	EmpLinkedList() : head(nullptr) {}
	//假定添加雇员时，id时自增长的，即id从小到大
	void add(Emp *emp)
	{ //如果链表为空...
		if (head == NULL)
		{
			head = emp;
			return;
		}
		//如果链表不为空，先找到最后一个节点
		Emp *temp = head;
		while (temp->next != nullptr)
		{
			temp = temp->next;
		}
		temp->next = emp;
		return;
	}

	//遍历链表
	void printList()
	{
		if (head == nullptr)
		{
			cout << "当前链表为空" << endl;
			return;
		}
		Emp *temp = head;
		while (temp != nullptr)
		{
			cout << "雇员 id=" << temp->id << "雇员的名字:" << temp->name << endl;
			temp = temp->next;
		}
		return;
	}
	//实现查找功能
	Emp *find(int id)
	{
		if (head == nullptr)
		{
			cout << "链表为空" << endl;
			return nullptr;
		}
		auto temp = head;
		while (temp != nullptr)
		{
			if (temp->id == id)
			{
				// cout<<"id:"<<temp->id<<"name:"<<temp->name<<endl;
				return temp;
			}
			temp = temp->next;
		}
		return nullptr;
	}

	void deleteNode(int id)
	{
		auto temp = this->head;
		auto tempDel = temp;
		if (this->head == nullptr) {
			cout << "链表为空，没有可供删除的节点" << endl;
			return;
		}
		//头节点就是要待删除的节点
		if (head->id == id) {
			temp = head->next;
			tempDel = head;
			head = temp;
			delete tempDel;
			cout << "节点删除成功" << endl;
			return;
		}
		//要找到待删除节点的前一个节点
		while (temp->next != nullptr) {
			//找到待删除节点的前一个节点
			if (temp->next->id == id) {
				tempDel = temp->next;
				temp->next = temp->next->next;
				delete tempDel;
				cout << "节点删除成功" << endl;
				return;
			}
			temp = temp->next;
		}
		//最后一个节点
		if (temp->id == id) {
			delete temp;
			temp = nullptr;
			cout << "节点删除成功" << endl;
			return;
		}
		cout << "链表中没有该节点" << endl;
		return;
	}

	bool isEmpty()
	{
		return head == nullptr;
	}

	~EmpLinkedList()
	{
		Emp *temp, *tempNext;
		temp = head;
		while (temp != nullptr)
		{
			tempNext = temp->next;
			delete temp;
			temp = tempNext;
		}
		head = nullptr;
	}

private:
	Emp *head;
};
//哈希表
class hashTable
{
public:
	hashTable(int size) : size(size)
	{
		hashListArr = new EmpLinkedList *[this->size];
		for (int i = 0; i < this->size; i++)
		{
			hashListArr[i] = new EmpLinkedList();
		}
	}

	void add(Emp *emp)
	{
		hashListArr[hashFun(emp->id)]->add(emp);
	}
	//哈希函数，最简单的哈希函数，取模法
	int hashFun(int id)
	{
		return id % size;
	}
	//遍历哈希列表
	void printHash()
	{
		for (int i = 0; i < (this->size); i++)
		{
			if (!hashListArr[i]->isEmpty())
			{
				hashListArr[i]->printList();
			}
		}
	}

	void find(int id)
	{
		int findId = hashFun(id);
		Emp *temp = hashListArr[findId]->find(id);
		if (temp == nullptr)
		{
			cout << "哈希表中没有该元素" << endl;
			return;
		}
		else
		{
			cout << "id: " << id << "name: " << temp->name << endl;
		}
	}

	void deleteNode(int id)
	{
		int deleteId = hashFun(id);
		hashListArr[deleteId]->deleteNode(id);
		return;
	}

	~hashTable()
	{
		if (hashListArr != nullptr)
		{
			delete[] hashListArr;
			hashListArr = nullptr;
		}
	}

private:
	//指针的数组
	EmpLinkedList **hashListArr;
	int size;
};

int main(int argc, char **argv)
{
	//做一个菜单
	int receive = 0;
	//用于生成员工的默认id
	int index = 0;
	hashTable *hash = new hashTable(5);
	Emp *empTemp;
	string name;
	while (true)
	{
		cout << "***请按照菜单，输入一个选项***" << endl;
		cout << "****加入员工信息  请输入1*****" << endl;
		cout << "***打印所有员工信息  请输入2***" << endl;
		cout << "***查询员工信息  请输入3***" << endl;
		cout << "****删除员工信息，请输入4****" << endl;
		cout << "********退出，请输入9*********" << endl;
		cin >> receive;
		// cout << "receive=" << receive << endl;
		// cout << "name=" << name << endl;
		int id = 0;
		switch (receive)
		{
		case 1:
			// c++11新加的 to_string函数，可用于字符串和数字拼接
			name = string("daniel") + std::to_string(index);
			empTemp = new Emp(index, name);
			hash->add(empTemp);
			index++;
			break;
		case 2:
			hash->printHash();
			break;
		case 3:
			cout << "请输入查询员工的id值" << endl;
			cin >> id;
			hash->find(id);
			break;
		case 4:
			cout << "请输入要删除员工的id值" << endl;
			cin >> id;
			hash->deleteNode(id);
			break;
		default:
			cout << "输入数字有误" << endl;
			break;
		}
		if (receive == 9)
		{
			break;
		}
		system("pause");
		system("cls");
	}
	if (hash != nullptr)
	{
		delete hash;
		hash = nullptr;
	}
}